package com.cris.sorting;

/**
 * Created by owen on 2017/3/7.
 */
public class MergeSort {
    private static Comparable []aux;
    public static void sort(Comparable []a){
        aux = new Comparable[a.length];
        sort(a,0,a.length-1);
    }
    public static void sort(Comparable []a,int lo,int hi){
        if(lo>=hi) return;
        int mid = lo + (lo+hi)/2;
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        if(less(a[mid+1],a[mid]))
            merge(a,lo,mid,hi);
    }

    public static void merge(Comparable []a,int lo,int mid,int hi){
        //copy the array
        for (int i = 0; i <a.length ; i++) {
            aux[i] = a[i];
        }
        int i = lo;
        int j = mid+1;
        for (int k = lo; k <hi ; k++) {
            if(i>mid) a[k] = aux[j++];
            else if(j>hi) a[k]= aux[i++];
            else if(less(aux[i],aux[j])) a[k] = aux[i++];
            else a[k] = aux[j++];
        }


    }
    //return true if v<w,else return false
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    private static void exch(Comparable []a,int i,int j){
        Comparable t = a[i]; a[i] = a[j]; a[j]=t;
    }
    private static void show(Comparable []a){
        for (int i=0;i<a.length;i++){
            System.out.print(a[i]+"");
        }
    }
    public static boolean isSorted(Comparable []a){
        for(int i = 1;i<a.length;i++){
            if(less(a[i],a[i-1])) return false;
        }
        return true;
    }
}
